package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;

public class LeetCodeMain63 {
    public boolean wordBreak(String s, Set<String> dict) {
        int length=s.length();
        boolean[] dp=new boolean[length+1];
        dp[0]=true;
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j]==true&&dict.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[length];
    }
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int length1=triangle.size();
        if (length1==1){
            return triangle.get(0).get(0);
        }
        int length2=triangle.get(length1-1).size();
        int[][] dp=new int[length1][length2];
        dp[0][0]=triangle.get(0).get(0);
        for (int i = 1; i < length1; i++) {
            for (int j = 0; j <=i; j++) {
                if (j==i){
                    dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(j);
                }else if (j==0){
                    dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);
                }else {
                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
                }
            }
        }
        Arrays.sort(dp[length1-1]);
        return dp[length1-1][0];
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        ArrayList<Integer> arrayList=new ArrayList<>();
        ArrayList<Integer> arrayList1=new ArrayList<>();
        ArrayList<Integer> arrayList2=new ArrayList<>();
        ArrayList<Integer> arrayList3=new ArrayList<>();

        arrayList.add(20);
        list.add(arrayList);

        arrayList1.add(30);
        arrayList1.add(40);
        list.add(arrayList1);

        arrayList2.add(60);
        arrayList2.add(50);
        arrayList2.add(70);
        list.add(arrayList2);

        arrayList3.add(40);
        arrayList3.add(10);
        arrayList3.add(80);
        arrayList3.add(30);
        list.add(arrayList3);

        LeetCodeMain63 main63=new LeetCodeMain63();
        System.out.println(main63.minimumTotal(list));
    }
}
